import java.io.File;
import java.io.ObjectInputStream.GetField;
import java.util.Collection;
import java.util.HashSet;
import java.util.Collections;
import java.util.Scanner;

//new
public class Algoithm {
	/*private int N;
	private double tau;
	private double delta;
	private function f;*/
    boolean indicator;

	
	public static Complex[] fOnMinusSets(HashSet<Integer> A,HashSet<Integer> B,int n,function f)
	{
		HashSet<Integer> retSet=new HashSet<Integer>();
		Integer m;
		Complex C[]=new Complex[n];
		for(Integer ele:A)
			for(Integer b:B)
			{
				m=ele-b;
				while(m<0)
				{
					m=m+n;
				}
				m=m%n;
				if(!retSet.contains(m))
					retSet.add(m);
     		}
		for(Integer i:retSet){
			C[i]=f.apply(i);
			
		}
		return C;
		
	}
	
	
	
	
	
	
	public static HashSet<Integer> SFT(function f, double tau, double delta, double norm){
	    int n=f.get_n();
	    double A;
	    if(norm>1)
	     A=10;
	   
	    else
	      A=0.01;

	    
	 
		HashSet<Integer>[] ArrayOfSets;
		HashSet<Integer> UnionOfBs;
		
		
		Complex[] Q = new Complex[n];
		ArrayOfSets = generateQueries(n, tau/36,f.get_fnorm(), A*delta/((Math.log(n)/Math.log(2))*Math.pow(f.getSquaredNorm()/tau, 1.5)));
        
		
		UnionOfBs = new HashSet<Integer>();
		
		for(int i = 1; i<ArrayOfSets.length; i++)
			UnionOfBs.addAll(ArrayOfSets[i]);
		
		Q=fOnMinusSets(ArrayOfSets[0], UnionOfBs, n, f);
		
			
		return fixedQuriesSFT(n, tau, ArrayOfSets, Q);

	}
	
	
	public static HashSet<Integer> fixedQuriesSFT(int n, double tau,
			HashSet<Integer>[] arrayOfSets, Complex[] Q) {
		int arrsize=(int)Math.round(Math.log(n)/Math.log(2))+2/*1*/;
		int aprime;
	    int bprime;
	    boolean flag=true;
		HashSet<HashSet<Integer>>[] Candidate=new HashSet[arrsize];
		HashSet<HashSet<Integer>> currevrn=new HashSet<HashSet<Integer>>();
		HashSet<Integer> curr=new HashSet<Integer>();
		HashSet<Integer> retSet=new HashSet<Integer>();
		curr.add(0);
		curr.add(n);
		currevrn.add(curr);
		
		Candidate[0]=currevrn;
		
		
		
		//System.out.println("***");
		for (int l=0;l<Math.round(Math.log(n)/Math.log(2))+1;l++)
		{
			//System.out.println("this is i"+l);
			flag=true;
			for(HashSet<Integer> set: Candidate[l])
			{
				//System.out.println("*");
				//System.out.println("was here, done that");
				aprime=Collections.min(set);
				 bprime = Collections.max(set);
				 //System.out.println("min max");
				 //System.out.println("this is aprime"+aprime);
				 //System.out.println("this is bprime"+bprime);
				 //System.out.println(arrayOfSets[0].size());
				 if(Distinguish(n,aprime, (aprime+bprime)/2, tau, arrayOfSets[0], arrayOfSets[l+1], Q))
				 {
					// System.out.println("first if");
					 HashSet<Integer> temp=new HashSet<Integer>();
					 temp.add(aprime);
					 temp.add((aprime+bprime)/2);
					 if(flag)
					 {
						 Candidate[l+1]=new HashSet<HashSet<Integer>>();
						 flag=false;
					 }
					 
					 Candidate[l+1].add(temp);
					
					 
				 }
				 
				 if(Distinguish(n,(aprime+bprime)/2,bprime, tau, arrayOfSets[0], arrayOfSets[l+1], Q))
				 {
					// System.out.println("second if");
					 HashSet<Integer> temp=new HashSet<Integer>();
					 
					 
					 
					 
					 temp.add((aprime+bprime)/2);
					 temp.add(bprime);
					 
					 if(flag)
					 {
						 Candidate[l+1]=new HashSet<HashSet<Integer>>();
						 flag=false;
					 }
					 Candidate[l+1].add(temp);
					 
					 
				 }
				 
			}
		//System.out.println("ended looping");
		}
		
		//System.out.println("one more time!!!!!!" +(Candidate[(int)Math.round((Math.log(n)/Math.log(2)))]).size());
		
		
		for(HashSet<Integer> subset:Candidate[(int)Math.round((Math.log(n)/Math.log(2)))+1])
		{
			//System.out.println("Max"+Collections.max(subset));
			//System.out.println("Min"+Collections.min(subset));
			if(Collections.max(subset)==Collections.min(subset))
			{
				retSet.add(Collections.max(subset));
			}
		}
		
	 return retSet;
	}
	
	
	
	
	
	
	






/*	public static HashSet<Double> fixedQuriesSFT(int n, double tau,
			HashSet<Integer>[] arrayOfSets, Complex[] q) {
		
		
		
		HashSet<HashSet<Double>> setOfSets, next;
		HashSet<Double> ret;
		HashSet<Double> Candidate;
		
		setOfSets = new HashSet<HashSet<Double>>();
		Candidate = new HashSet<Double>();
		Candidate.add((double) 0);
		Candidate.add((double) n);
		setOfSets.add(Candidate);
		//-1 was added
		for(int l = 0; l<(Math.log(n)/Math.log(2))-1; l++){
	
			next = new HashSet<HashSet<Double>>();
			for (HashSet<Double> currSet: setOfSets) {
				double a = Min(currSet), b = Max(currSet);
				if(Distinguish(a, (a+b)/2, tau, arrayOfSets[0], arrayOfSets[l+1], Q)) {
					Candidate = new HashSet<Double>();
					Candidate.add(a);
					Candidate.add((a+b)/2);
					next.add(Candidate);
				}
				if(Distinguish((a+b)/2+1, b, tau, arrayOfSets[0], arrayOfSets[l+1], Q)) {
					Candidate = new HashSet<Double>();
					Candidate.add((a+b)/2+1);
					Candidate.add(b);
					next.add(Candidate);
				}
			}
			setOfSets = next;
		}
		ret = new HashSet<Double>();
		System.out.println(setOfSets.size());
		for(HashSet<Double> s: setOfSets) {
			System.out.println("Size: " + s.size() + " ; Min: " + Min(s) + " ; Max: " + Max(s));
			if(s.size()==1)
				ret.add(Min(s));
		}
		return ret;
		
		
		
		
		
		return null;
	}*/






	public static HashSet<Integer>[] generateQueries(int n, double gamma, double norm, double delta) {
		
		long arrsize=Math.round(Math.log(n)/Math.log(2));
		HashSet<Integer>[] ret_arr = new HashSet[(int)arrsize+/*1*/2];
		
		int mA;
		int mB;
		
		if(norm<=1)
		{
		double A=0.002;
		double B=0.9;
		 mA = (int) ((A/(gamma*gamma))*Math.log(1/delta)) + 1;
		 mB = (int) ((B/(gamma*gamma))*Math.log(1/(delta*gamma))) + 1;
		}
		
		else{
		double eta1=Math.min(gamma, Math.sqrt(gamma));
		double eta=Math.min(eta1, gamma/norm);
		System.out.println("norm"+norm);
		
		double tmpCoeff = Math.pow(norm/eta, 2);

		
		
		//System.out.println("e"+eta);
		//System.out.println("tc"+tmpCoeff);
		 mA = (int) ((0.00002) * Math.ceil(tmpCoeff*Math.log(1.0/delta))/Math.log(2));
		 mB = (int) ((0.000002) * Math.ceil(tmpCoeff*Math.log(norm/(delta*gamma))/Math.log(2)));	

		
		}
		
			mA = Math.min(mA, n); //mA % n;
		
		
		
		System.out.println("ma"+mA);
		System.out.println("mb"+mB);
		
		//System.out.println("!!!this is mA"+mA);
		ret_arr[0] =HelperClass.getRandomSet(mA, n);
		
	
		
		for (int i = 1; i < ret_arr.length; i++) {
			ret_arr[i] = HelperClass.getRandomSet((int) Math.min(mB, Math.pow(2, i-1)),(int) Math.pow(2, i-1));
			
		}
		
		return ret_arr;
		
		
		
	}
	
	private static boolean Distinguish(int n, double a, double b, double tau, HashSet<Integer> A, HashSet<Integer> B, Complex[] Q){
		
		//System.out.println("distinguishing!");
		double convolution = 0;
		/*System.out.println("a");
		System.out.println(n);
		System.out.println(a);
		System.out.println(b);
        System.out.println(tau);
        System.out.println("a");
        System.out.println("size of A"+A.size());
        System.out.println("size of B"+B.size());
        System.out.println("size of Q"+Q.length);
		*/
		for (int x : A) {
		
			Complex sum = new Complex(0,0);
			
		for (int y : B) {
				int q = (x-y) % Q.length;
				if(q<0)
					q += Q.length;
				sum.add(Complex.multiply(Complex.Chi(Math.floor((a+b)/2), y,n), Q[q]));
			}
			
			convolution += Math.pow(sum.magnitude()/B.size(),2);
		}
		
		convolution = convolution/A.size();
		
		//System.out.println("this is convolution:"+convolution);
		return convolution>=5*tau/36;
	}
	
	
	
	
	public static void main(String[] args) {
		
		Scanner read=new Scanner(System.in);
		String str;
		boolean XMLflag;
		double tau;
		double fnorm;
		double delta;
		int n;
		System.out.println("Please press 0 if you wish to enther the values of the function via");
		System.out.println("XML FILE. Please press 1 if you would like to enter values on the fly");
		
		
			
		str=read.next();
		if(str.equals("0")){
			System.out.println("Reading data via XML File");
			System.out.println("Please enter the address of the XML FILE");
			str=read.next();
			XMLflag=true;}
		else{
			System.out.println("on the fly");
			XMLflag=false;}
		System.out.println("Please enter n: the cardinal of the cyclic group");
		n=read.nextInt();
		
		System.out.println("Please insert tau- tau is the thershold");
		tau=read.nextDouble();
		
		System.out.println("Please insert delta");
		delta=read.nextDouble();
		System.out.println("Please insert the supremal norm of the function");
		fnorm=read.nextDouble();
		
		if(XMLflag==true){
		XML x;
		HashSet<Integer> l;
		try {
			
			
			 x = new XML(n, new File(str));
		
			 
			   function f=x.getFunction();
			   f.set_fnorm(fnorm);
			   f.set_xml(true);

			  
			   l=Algoithm.SFT(f,tau,delta, fnorm);
			  // System.out.println("111");

			   System.out.println("This is the outuput of the algorithm:");
				for(Integer smtsmut:l)
				{
					System.out.println(smtsmut);
					
				}
			
				

		} catch (Exception e) {System.out.println(e);}

		System.exit(0);
		}
		
		 function f=new function(n);
		 HashSet<Integer>l=Algoithm.SFT(f,tau,delta, fnorm);

		   System.out.println("This is the outuput of the algorithm:");
			for(Integer smtsmut:l)
			{
				System.out.println(smtsmut);
				
			}
		
		
		
	

		
	
		
	}		
		
		
		
	}
	
	















